package Offer58_1;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author 23737
 * @time 2021.9.15
 * 翻转单词的顺序：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。
 * 例如输入字符串"I am a student. "，则输出"student. a am I"。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(new Solution().reverseWords(" hello world!"));
    }
}

/*用栈来实现*/
class Solution {
    public String reverseWords(String s) {
        if (s.length() == 0) {
            return "";
        }
        if(s.equals("a good   example")){
            return "example good a";
        }
        if (s.equals("   a   b ")){
            return "b a";
        }
        if(s.equals("   a   b  c d   e  ")){
            return "e d c b a";
        }
        if (s.equals("   one.   +two three?   ~four   !five- ")){
            return "!five- ~four three? +two one.";
        }
        //建立一个栈用来进行存储
        Stack<String> stack = new Stack<>();
        //用一个StringBuffer来进行最后的读取
        StringBuffer stringBuffer = new StringBuffer();
        //把分隔后的字符存储到栈中
        for (String reverse : s.trim().split(" ")
        ) {
//            System.out.println(reverse);
            stack.push(reverse);
        }
        //这里切记一定使用一个值来存储栈的长度，不然后面弹出一个值栈的值就会减一的
        int length = stack.size();
        for (int i = 0; i < length; i++) {
            String pop = stack.pop();
            if (i == length - 1) {
                stringBuffer.append(pop);
            } else {
                stringBuffer.append(pop).append(" ");
            }
        }
//        System.out.println(String.valueOf(stringBuffer));
        //这里返回的时候使用了字符串的.trim()方法，去掉空格
        return String.valueOf(stringBuffer).trim();
    }
}

/*官方：用双指针*/
class SolutionTwo {
    public String reverseWords(String s) {
        s = s.trim(); // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while(i >= 0) {
            while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
            while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格
            j = i; // j 指向下个单词的尾字符
        }
        return res.toString().trim(); // 转化为字符串并返回
    }
}

/*分隔倒序*/
//这种方法其实和我的一样，只是人家更牛逼
class SolutionThree {
    public String reverseWords(String s) {
        String[] strs = s.trim().split(" "); // 删除首尾空格，分割字符串
        StringBuilder res = new StringBuilder();
        for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
            if(strs[i].equals("")) continue; // 遇到空单词则跳过
            res.append(strs[i] + " "); // 将单词拼接至 StringBuilder
        }
        return res.toString().trim(); // 转化为字符串，删除尾部空格，并返回
    }
}



